/*
 *Description:
 *User:laoHu
 *Created with Intellij IDEA 2025
 *@pragma
 */

public class Main {
    /**
     * 大数加法
     * @param s 操作数1
     * @param t 操作数2
     * @return 返回和的字符串
     */
    public String solve(String s, String t) {

        int i = s.length() - 1;
        int j = t.length() - 1;

        int tem = 0;

        StringBuilder ret = new StringBuilder();

        while (i >= 0 || j >= 0 || tem != 0) {
            if (i >= 0) tem += s.charAt(i--) - '0';
            if (j >= 0) tem += t.charAt(j--) - '0';

            ret.append((char) ((tem % 10) + '0'));

            tem /= 10;
        }

        return ret.reverse().toString();
    }

    public static void main1(String[] args) {
        Main m = new Main();
        m.solve("99", "1");
    }

    static class ListNode{
        ListNode next;
        int val;
        public ListNode(int val) {
            this.val = val;
        }
    }
    //1.逆序链表:创建一个虚拟头节点
    public ListNode reverse(ListNode head){

        ListNode newHead = new ListNode(0);

        ListNode cur = head;

        while(cur != null){

            ListNode next = cur.next;
            cur.next = newHead.next;
            newHead.next = cur;
            cur = next;

        }

        return newHead.next;
    }

    /**
     * 链表相加
     * https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=196&tqId=37147&ru=/exam/oj
     * @param head1 链表1
     * @param head2 链表2
     * @return 和
     */
    public ListNode addInList (ListNode head1, ListNode head2) {

        //2.逆序链表
        head1 = reverse(head1);
        head2 = reverse(head2);

        //3.遍历链表
        int t = 0;
        //ret是虚拟头节点
        ListNode ret = new ListNode(0),prev = ret;
        while(head1 != null || head2 != null || t != 0){

            if(head1 != null){
                t += head1.val;
                head1 = head1.next;
            }
            if(head2 != null){
                t += head2.val;
                head2 = head2.next;
            }

            prev = prev.next = new ListNode(t % 10);
            t /= 10;
        }
        return reverse(ret.next);
    }

    public static void main(String[] args) {
        StringBuilder s = new StringBuilder("aa");
        s.length();


        char[] s1 = new StringBuilder("aa").reverse().toString().toCharArray();
    }

    /**
     * 大数乘法
     * https://www.nowcoder.com/practice/c4c488d4d40d4c4e9824c3650f7d5571?tpId=196&tqId=37177&ru=/exam/oj
     * @param s 操作数1
     * @param t 操作数2
     * @return  返回乘法结果
     */
    public String solve1 (String s, String t) {

        //1.逆序转为字符数组
        char[] s1 = new StringBuilder(s).reverse().toString().toCharArray();
        char[] t1 = new StringBuilder(t).reverse().toString().toCharArray();

        //2.无进制相乘
        int n = s1.length;
        int m = t1.length;

        int[] tem = new int[n + m];

        for(int i = 0;i < n;i++){
            for(int j = 0; j< m;j++){
                tem[i + j] += (s1[i] - '0') * ( t1[j] - '0');
            }
        }

        //3.转换进制
        StringBuilder ret = new StringBuilder();
        int sum = 0;
        for(int x : tem){
            sum += x;
            ret.append(sum % 10);
            sum /= 10;
        }

        //4.处理末尾为 0 情况
        while(ret.length() > 1 && ret.charAt(ret.length() -1) == '0'){

            ret.deleteCharAt(ret.length() - 1);
        }

        return ret.reverse().toString();
    }
}
